package 中等.搜索.广度优先搜索;

import util.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：
 * <p>
 * 二叉树根节点所在层下标为 0 ，根的子节点所在层下标为 1 ，根的孙节点所在层下标为 2 ，依此类推。
 * 偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增
 * 奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减
 * 给你二叉树的根节点，如果二叉树为 奇偶树 ，则返回 true ，否则返回 false 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/even-odd-tree
 */
public class 奇偶树_1609 {

    public static void main(String[] args) {

        TreeNode root = new TreeNode(5);
        TreeNode node4 = new TreeNode(4);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node33 = new TreeNode(3);
        TreeNode node7 = new TreeNode(7);
        root.right = node2;
        root.left = node4;
        node2.left = node7;
        node4.right = node3;
        node4.left = node33;
        System.out.println(efficientIsEvenOddTree(root));

    }

    /**
     * 广度优先搜索+队列
     *
     * @param root
     * @return
     */
    public static boolean isEvenOddTree(TreeNode root) {
        int tier = 0;  //记录层数
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.addLast(root);  //使用队列的方式，先进先出
        while (!deque.isEmpty()) {
            int size = deque.size();
            Integer preNodeValue = null;
            while (size-- > 0) {  //取出上一层
                TreeNode curNode = deque.pollFirst();
                if (tier % 2 == 0) {  //偶数层
                    if (curNode.val % 2 == 0) {
                        return false;
                    }
                    if (preNodeValue != null) {
                        if (curNode.val <= preNodeValue) {
                            return false;
                        }
                    }
                    preNodeValue = curNode.val;
                } else {  //奇数层
                    if (curNode.val % 2 != 0) {
                        return false;
                    }
                    if (preNodeValue != null) {
                        if (curNode.val >= preNodeValue) {
                            return false;
                        }
                    }
                    preNodeValue = curNode.val;

                }
                if (curNode.left != null) {
                    deque.addLast(curNode.left);  //左子节点先进先出
                }
                if (curNode.right != null) {
                    deque.addLast(curNode.right);
                }
            }
            tier++;  //进入下一层
        }
        return true;
    }

    /**
     * 让代码更加简洁
     *
     * @param root
     * @return
     */
    public static boolean efficientIsEvenOddTree(TreeNode root) {
        int tier = 0;  //记录层数
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);  //使用队列的方式，先进先出
        while (!deque.isEmpty()) {
            int size = deque.size();
            //偶数层是递增的，所以取最小值比较
            int preNodeValue = tier % 2 == 0 ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            while (size-- > 0) {  //取出上一层
                TreeNode curNode = deque.pollFirst();
                int curNodeValue = curNode.val;
                if (tier % 2 == curNodeValue % 2) {  //奇数层的值不能是奇数，偶数层值不能是偶数
                    return false;
                }
                if ((tier % 2 == 0 && curNodeValue <= preNodeValue) || (tier % 2 == 1 && curNodeValue >= preNodeValue)) {  //偶数层
                    return false;
                }
                preNodeValue = curNode.val;
                if (curNode.left != null) {
                    deque.offer(curNode.left);  //左子节点先进先出
                }
                if (curNode.right != null) {
                    deque.offer(curNode.right);
                }
            }
            tier++;  //进入下一层
        }
        return true;
    }

}
